<?php
/**
 * @title 29.两数相除 - 减法
 * @author start2004
 */

class Solution {

    /**
     * @param Integer $dividend
     * @param Integer $divisor
     * @return Integer
     */
    function divide($dividend, $divisor) {
        $max = pow(2, 31)-1;
        $min = -1-$max;

        /**
         * @since 2020-07-03 -2^31/-1 = 2^31, 溢出处理
         */
        if($dividend == $min AND $divisor == -1){
            return $max;
        } else {}

        /**
         * @since 2020-07-03 处理分母最大负数, 这样分母可以取正
         */
        if($divisor == $min){
            if($dividend == $min){
                return 1;
            } else {
                return 0;
            }
        } else {}

        /**
         * @since 2020-07-03 确定结果的正负号
         * @since 2020-07-03 分子处理成无符号字符串, 不能abs, 可能会溢出
         * @since 2020-07-03 分母已排除最大负数, 不会溢出
         */
        $a = (string) $dividend;
        $b = abs($divisor);
        $symbol = true;
        if($dividend<0){
            $symbol = !$symbol;
            $a = substr($a, 1);
        } else {}
        if($divisor<0){
            $symbol = !$symbol;
        } else {}

        /**
         * @since 2020-07-03 开始比较
         */
        $lenA = strlen($a);
        $lenB = strlen((string) $b);

        /**
         * @since 2020-07-03 abs(a) < abs(b), 返回0
         */
        if($lenA < $lenB){
            return 0;
        } else {}

        /**
         * @since 2020-07-03 结果集
         */
        if($symbol){
            $valArray = [];
        } else {
            $valArray = ["-"];
        }

        /**
         * @since 2020-07-03 初始化
         */
        $add = substr($a, 0, $lenB);
        $i = $lenB-1;
        // echo "分子={$a}, 长度={$lenA}, 分母={$b}, 长度={$lenB}", str_repeat(PHP_EOL, 2);
        // while($i<$lenA){
        while(true){
            $val = 0;

            /**
             * @since 2020-07-03 凑齐相同长度lenB或者lenB+1, 循环减b, 得到本次商和余数
             * @since 2020-07-03 避免分子abs溢出, 使用负数
             */
            $newA = intval("-". $add);
            // $currentA = $newA;
            while( ($newA = $newA+$b) <= 0){
                $val++;
            }

            /**
             * @since 2020-07-03 保存结果集
             */
            $valArray[] = $val;

            /**
             * @since 2020-07-03 本次余数
             */
            $add = (string) ($b-$newA);
            // $addlen = strlen($add);
            // echo "i={$i}, 分子={$currentA}, 商={$val}, 余数={$add}", PHP_EOL;

            /**
             * @since 2020-07-03 本次余数和b长度差值<=1, 正常循环
             */
            $morelen = max(1, $lenB-strlen($add));
            // if($morelen <= 1) {
            //     $i++;
            //     $add = $add . $a[$i];
            // } else {
            /**
             * @since 2020-07-03 超过1, 跳跃增加
             */
            // echo "morelen = {$morelen}", PHP_EOL;

            /**
             * @since 2020-07-03 a所有剩余长度都不够
             */
            // if($i+$morelen >= $lenA){
            if(($i+$morelen) >= $lenA){
                /**
                 * @since 2020-07-03 补0结束
                 */
                // echo "后续长度不够, 补", ($lenA-1-$i) ,"个0, break";
                $valArray[] = str_repeat("0", $lenA-1-$i);
                break;
            } else {
                /**
                 * @since 2020-07-03 add增加morelen-1个长度, 结果集补morelen-1个0
                 */
                $valArray[] = str_repeat("0", $morelen-1);
                $add = $add . substr($a, $i+1, $morelen);
                $i = $i+$morelen;
                // echo "补", ($morelen-1) ,"个0, add={$add}, i={$i}", PHP_EOL;
            }
            // }
        }

        /**
         * @return
         */
        $result = intval(implode("", $valArray));
        return $result;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.03_2.php
 */
$datas = [
    [10, 3],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->divide($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
